﻿#include <iostream>
using namespace std;

template<class T>
class Node {
public:
	Node() {}
	Node* pre;
	Node* next;
	
	void setData(T data) { this->data = data; }
	T getData() { return this->data; }
private:
	T data;
};

template<class P>
class dList {
public:
	dList();
	bool isEmpty();
	Node<P>* getNode(int index);
	int size();
	void insert(int data, int index);
	void traversal();
	void remove(int index);
	void modify(int data,int index);

private:
	Node<P>* head;
};

template<class P>
dList<P>::dList() {
	// 创建头结点
	head = new Node<P>();
	head->pre = NULL;
	head->next = NULL;
	head->setData(0);
}

template<class P>
bool dList<P>::isEmpty() {
	if (head->next == NULL) {
		return true;
	}
	else
	{
		return false;
	}
}

template<class P>
int dList<P>::size() {
	if (isEmpty()) {
		return 0;
	}
	else {
		int count = 0;
		Node<P>* current = head->next;

		while (current != NULL)
		{
			current = current->next;
			count++;
		}
		return count;
	}
}

template<class P>
Node<P>* dList<P>::getNode(int index) {
	Node<P>* current = head;
	int currentCount = 0;

	while (currentCount <= index)
	{
		current = current->next;
		currentCount++;
	}
	return current;
}

template<class P>
void dList<P>::insert(int data, int index) {
	Node<P>* node = new Node<P>();
	node->setData(data);
	// 1、列表为空时
	if (isEmpty()) {
		head->next = node;
		node->pre = head;
		return;
	}
	// 2、头插法
	if (index == 0) {
		node->next = head->next;
		head->next->pre = node;
		node->pre = head;
		head->next = node;
	}
	// 3、尾插法
	else if (index >= this->size() - 1) {
		Node<P>* temp = this->getNode(this->size() - 1);
		temp->next = node;
		node->pre = temp;
	}
	// 4、任意位置插入
	else
	{
		Node<P>* pre = this->getNode(index-1);
		Node<P>* next = pre->next;
		node->next = pre->next;
		node->pre = pre;
		pre->next = node;
		node->next->pre = node;
	}
}

template<class P>
void dList<P>::remove(int index) {
	if ((index < (this->size() - 1)) && (index > 0)) {
		Node<P>* node = this->getNode(index);
		Node<P>* pre = node->pre;
		Node<P>* next = node->next;
		pre->next = next;
		next->pre = pre;
	}
}

template<class P>
void dList<P>::traversal() {
	if (!isEmpty()) {
		Node<P>* current = head->next;
		while (current)
		{
			cout << current->getData() << "  ";
			current = current->next;
		}
		cout << endl;
	}
}

template<class P>
void dList<P>::modify(int data,int index) {
	Node<P>* temp = this->getNode(index);
	temp->setData(data);
}

int main() {
	dList<int> b;
	
	b.insert(2, 0);
	b.insert(3, 1);
	b.insert(4, 2);
	b.insert(5, 3);
	b.traversal();

	b.remove(2);
	b.traversal();

	b.modify(1, 1);
	b.traversal();


	b.insert(3, 7);
	b.traversal();
}


